package jianzhi

func maxDepth(root *TreeNode) int {

	if root == nil {
		return 0
	}

	level := [][]int{}
	var levelLen int

	queue := []*TreeNode{root}

	for len(queue) != 0 {
		temp := []int{}
		levelLen = len(queue)
		for i := 0; i < levelLen; i++ {
			temp = append(temp, queue[i].Val)
			if queue[i].Left != nil {
				queue = append(queue, queue[i].Left)
			}
			if queue[i].Right != nil {
				queue = append(queue, queue[i].Right)
			}
		}
		level = append(level, temp)
		queue = queue[levelLen:]
	}

	return len(level)

}

func maxDepth2(root *TreeNode) int {
	if root == nil {
		return 0
	}

	leftDepth := maxDepth2(root.Left)
	rightDepth := maxDepth2(root.Right)

	if leftDepth > rightDepth {
		return leftDepth + 1
	}

	return rightDepth + 1

}
